/***
题目链接：分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
https://leetcode-cn.com/problems/partition-list-lcci/
***/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        //不会分治，只能耗费内存
        ListNode* small = new ListNode(0);//初始化节点值为0的空节点.
        ListNode* large = new ListNode(0);
        ListNode* small_start = small;
        ListNode* large_start = large;
        if (!head) return nullptr;
        while(head){
            if(head->val < x){
                small->next = head;
                small = small->next;
            }else{
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = nullptr;
        small->next = large_start->next;
        return small_start->next;
    }
};
执行用时：4 ms, 在所有 C++ 提交中击败了 88.61%的用户
内存消耗：9.9 MB, 在所有 C++ 提交中击败了 86.09%的用户